#pragma once
#include <iostream>
#include <vector>
using namespace std;


enum colour
{
	RED,
	BLACK
};

template <class T>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _perant;

	T _kv;
	colour col;
	RBTreeNode(const T& kv)
		:_kv(kv), col(RED), _left(nullptr), _right(nullptr), _perant(nullptr)
	{ }
};

template<class T, class P, class Y>
class Iterator
{
public:
	typedef Iterator<T, P, Y> Self;
	typedef RBTreeNode<T> Node;

	Iterator(Node* x, Node* root = nullptr)
		:_it(x), _root(root)
	{ }
	Iterator()
		:_it(nullptr), _root(nullptr)
	{ }

	Self& operator=(Node* x)
	{
		_it = x;
		return *this;
	}

	Y operator*()
	{
		return _it->_kv;
	}

	P operator->()
	{
		return &_it->_kv;
	}

	bool operator!=(const Self& x)
	{
		return x._it != _it;
	}

	bool operator==(const Self& x)
	{
		return x._it == _it;
	}

	Self& operator++()
	{
		if (_it->_right != nullptr)
		{
			Node* cur = _it->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_it = cur;
		}
		else
		{
			Node* cur = _it;
			Node* perant = cur->_perant;

			if (cur == perant->_left) _it = perant;
			else
			{
				while (perant && cur == perant->_right)
				{
					cur = perant;
					perant = perant->_perant;
				}
				_it = perant;
			}
		}
		return *this;
	}

	Self& operator++(int)
	{
		Node* it = _it;
		++(*this);
		return Self(it);
	}

private:
	Node* _it;
	Node* _root;
};

//-----------------------------------------------------
template<class K, class T, class Key>
class RBTree
{

	
	Key kot;
public:
	typedef typename RBTreeNode<T> Node;
	typedef typename Iterator<T, T*, T&> iterator;
	typedef typename Iterator<const T, const T*, const T&> const_iterator;

	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	RBTree(const RBTree<K, T, Key>& t)
	{
		_root = Copy(t._root);
	}

	RBTree<K, T, Key>& operator=(RBTree<K, T, Key> t)
	{
		swap(_root, t->_root);
		swap(_size, t->_size);
		return *this;
	}

	RBTree() = default;

	iterator begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur, _root);
	}

	iterator end()
	{
		return iterator(nullptr, _root);
	}

	pair<iterator, bool> insert(const T& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->col = BLACK;
			_size++;
			return make_pair(iterator(_root), 1);
		}
		Node* cur = _root, * perant = nullptr;
		while (cur)
		{
			if (kot(cur->_kv) > kot(kv))
			{
				perant = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_kv) < kot(kv))
			{
				perant = cur;
				cur = cur->_right;
			}
			else return make_pair(iterator(cur), 0);
		}
		_size++;
		cur = new Node(kv);
		Node* newnode = cur;
		if (kot(perant->_kv) > kot(kv)) perant->_left = cur;
		else perant->_right = cur;
		cur->_perant = perant;
		while (perant && perant->col == RED)
		{
			Node* g = perant->_perant;
			if (g->_left == perant)
			{
				Node* u = g->_right;
				if (u && u->col == RED) 
				{
					perant->col = u->col = BLACK;
					g->col = RED;
					cur = g;
					perant = cur->_perant;
				}
				else
				{
					if (cur == perant->_left)
					{
						RotateL(g);
						cur->col = g->col = RED;
						perant->col = BLACK;
					}
					else
					{
						RotateR(perant);
						RotateL(g);
						cur->col = BLACK;
						perant->col = g->col = RED;
					}
					
				}
			}
			else
			{
				Node* u = g->_left;
				if (u && u->col == RED)
				{
					u->col = perant->col = BLACK;
					g->col = RED;
					cur = g;
					perant = cur->_perant;
				}
				else
				{
					if (cur == perant->_right)
					{
						RotateR(g);
						cur->col = g->col = RED;
						perant->col = BLACK;
					}
					else
					{
						RotateL(perant);
						RotateR(g);
						cur->col = BLACK;
						perant->col = g->col = RED;
					}
				}
			}
		}
		_root->col = BLACK;
		return make_pair(iterator(newnode), 1);
	}

	iterator find(const K& k)
	{
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_kv) > k)
			{
				cur = cur->_left;
			}
			else if (kot(cur->_kv) < k)
			{
				cur = cur->_right;
			}
			else return iterator(cur);
		}

		return  iterator(nullptr);
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << "____________________________________" << endl;
	}

	size_t size() { return _size; }

	bool IsRBTree()
	{
		int ans = 0;
		Node* cur = _root;
		while (cur)
		{
			ans += (cur->col == BLACK);
			cur = cur->_left;
		}
		return _IsRBTree(_root, 0, ans);
	}

private:
	Node* Copy(const Node* t)
	{
		if (t == nullptr) return nullptr;
		Node* root = new Node(t->_kv);
		root->col = t->col;
		root->_left = Copy(t->_left);
		if (root->_left != nullptr)
			root->_left->_perant = root;

		root->_right = Copy(t->_right);
		if (root->_right != nullptr)
			root->_right->_perant = root;

		return root;
	}

	void Destroy(Node* root)
	{
		if (!root) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

	bool _IsRBTree(Node* root, int sum,const int ans)
	{
		if (root == nullptr) return sum == ans;
		int x = (root->col == BLACK);
		return ((root->col == RED && root->_perant->col != RED) || (root->col == BLACK)) &&
			_IsRBTree(root->_left, sum + x, ans) && _IsRBTree(root->_right, sum + x, ans);
	}

	void _InOrder(Node* root)
	{
		if (!root) return;
		_InOrder(root->_left);
		cout << root->_kv.first << ':' << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	void RotateL(Node* root)
	{
		Node* Perant = root->_perant;
		Node* SubL = root->_left;
		Node* SubLR = SubL->_right;
		if (SubLR != nullptr)
			SubLR->_perant = root;
		root->_left = SubLR;
		root->_perant = SubL;
		if (Perant != nullptr)
		{
			if (Perant->_left == root) Perant->_left = SubL;
			else Perant->_right = SubL;
		}
		else
		{
			_root = SubL;
		}
		SubL->_perant = Perant;
		SubL->_right = root;
	}

	void RotateR(Node* root)
	{
		Node* SubR = root->_right;
		Node* SubRL = SubR->_left;
		Node* Perant = root->_perant;
		if (SubRL != nullptr)
			SubRL->_perant = root;
		root->_perant = SubR;
		root->_right = SubRL;
		if (Perant == nullptr)
		{
			_root = SubR;
		}
		else
		{
			if (Perant->_left == root) Perant->_left = SubR;
			else Perant->_right = SubR;
		}
		SubR->_perant = Perant;
		SubR->_left = root;
	}


private:
	Node* _root;
	size_t _size;
};

